package com.practice.sequence;

import java.util.ArrayList;

/**
 * Given an array A[i..j] find out maximum j-i such that A[i]<A[j] in O(n) time.
 */
public class MaxDistance {
	public int find(int[] a) {
		ArrayList<Integer> desc = new ArrayList<Integer>();
		int cur = a[0];
		desc.add(0);
		for (int i=1; i<a.length; i++) {
			if (a[i] < cur) {
				cur = a[i];
				desc.add(i);
			}
		}
		
		int maxD = -1;
		int end = a.length - 1;
		for (int i=desc.size()-1; i>=0; i--) {
			int j = desc.get(i);
			while (end > j) {
				if (a[end] > a[j]) {
					maxD = Math.max(maxD, end - j);
					break;
				}
				else {
					end--;
				}
			}
		}
		
		return maxD;
	}
}
